cells = [0]*50
cells[30] = 1
i = 34


def put():
    assert not (cells[i] & 2)
    cells[i] |= 2
def pick():
    assert cells[i] & 2
    cells[i] &= ~2
def left():
    global i
    i-=1
def right():
    global i
    i+=1
def wave():
    assert cells[i] & 1
    return True

def drawstate(f):
    x=''.join('$' if c & 1 else 
        ('!' if c & 2 else '.') 
        for c in cells)
    print '%16s: %s' % (f,x)
    print ' '*18+ ' '*i + '^'

#=======================================
# THE STATE MACHINE
#=======================================
def A(s):
    # here the direction is MUST be 0 on startup
    if s == '010':
        return wave, '0', A
    if s == '110':
        return wave, '1', A
    if s == '000':
        return put, '0', A
    if s == '001':
        return left, '1', A
    if s == '100':
        return put, '1', B

def B(s):
    if s == '110': 
        return wave, '1', B
    if s == '010':
        return wave, '0', B
    if s == '101':
        return pick, '1', C
    if s == '001':
        return pick, '0', C
    if s == '000':
        return right, '0', B
    if s == '100':
        return left, '1', B

def C(s):
    if s == '100':
        return left, '1', D
    if s == '000':
        return right, '0', D

def D(s):
    if s == '110':
        return wave, '1', D
    if s == '010':
        return wave, '0', D
    if s == '100':
        return put, '1', D
    if s == '000':
        return put, '0', D
    if s == '101':
        return right, '0', B
    if s == '001':
        return left, '1', B


#=======================================

success=False
next = A
cd = '0'
drawstate('init->A[R]')
while not success:
    tr = '1' if cells[i] & 1 else '0'
    fl = '1' if cells[i] & 2 else '0'
    curr = next
    cmd, nextdir, next = curr(cd+tr+fl)
    cd = nextdir
    success=cmd()
    drawstate('%s:%s->%s[%s]' % (curr.__name__, 
        cmd.__name__, next.__name__, {'0':'R', '1':'L'}[nextdir]))






